import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * 使用LinkedHashMap来实现LRU算法
 * LinkedHashMap在指定accessOrder之后每次在使用之后都会将最新使用的元素挂在队尾
 * 所以队首元素就是最少使用的元素
 */
public class LinkedHashMapLRU<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;

    public LinkedHashMapLRU(int cacheSize) {
        super(16, 0.75f, true); // 初始化LinkedHashMap，注意accessOrder要设置为true
        CACHE_SIZE = cacheSize;
    }

    /**
     * 什么时候移除队头元素
     * 当前设置的是size>cache_size时移除EldestEntry（即最少使用）
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > CACHE_SIZE;
    }

    public static void main(String[] args) {
        // 设置当前cache最大size为5
        LinkedHashMapLRU<Integer, Integer> cache = new LinkedHashMapLRU<>(5);
        // 链表初始化
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 4);
        cache.put(5, 5);
        print(cache); // data: 1 --> 2 --> 3 --> 4 --> 5

        System.out.println("获取元素 1");
        cache.get(1); // 访问一个条目，以更新 LRU 顺序
        print(cache); // 2 --> 3 --> 4 --> 5 --> 1

        System.out.println("添加元素 6");
        cache.put(6, 6); // 这将会替换 key 为 2 的条目，因为 2 在前，而 6 在尾
        print(cache);

        System.out.println("获取元素 3");
        cache.get(3);
        print(cache);

        System.out.println("-- 测试普通的LinkedHashMap --");
        LinkedHashMap<Integer, Integer> testMap = new LinkedHashMap<>();
        testMap.put(1, 1);
        testMap.put(2, 2);
        testMap.put(3, 3);
        testMap.put(4, 4);
        print(testMap);

        testMap.get(3);
        print(testMap);// 可以看到在不设置accessOrder时调用get方法是不会影响队列顺序的
    }

    // 打印链表信息
    private static void print(LinkedHashMap<Integer, ?> data) {
        System.out.print("data: ");
        Set<Integer> keySet = data.keySet();
        int count = 0;
        for (int key : keySet) {
            count++;
            System.out.print(key);
            if (count < keySet.size()) {
                System.out.print(" --> ");
            } else {
                System.out.println();
            }
        }
    }
}
